A disk scheduler manages a queue of pending disk access requests for input/output (I/O) data, deciding at which time and in which order to submit the requests to a storage device. Typically, access requests arrive at a processor in an ongoing stream from a plurality of applications. The access requests are typically addressed to logical blocks associated with storage locations in the storage device. Optionally, disk access requests contain a priority value. Disk access requests often also contain a deadline, which specifies a time by which the disk access request is to have completed processing.
Schedulers often try to minimize average total service time and maximize total system throughput. Additionally, when there are disk access requests with deadlines, the scheduler also attempts to ensure that all such requests are completed before their deadlines. Total service time is the time it takes from the receipt of an access request at a processor to the completion of data transfer in or out of the storage device. Total system throughput is associated with an average transfer rate of data in or out of the storage device. Total service time is a function of the time the request spends waiting in the queue at the scheduler. Total service time is also a function of the device mechanics, which include the seek and rotation distance separating the I/O head and the disk location associated with the block assigned to the I/O data. Total service time also includes the time to transfer the data in or out of the disk.
Schedulers often attempt to minimize the total service times for a group of requests by organizing the requests according to block location to minimize the seek and rotational delays between servicing blocks in the group of requests. A simplified scheduler often organizes the blocks according to an increasing sequence by logical block location. A simplified processing environment often only involves access requests having the same level of priority. However, disk access requests can have different priorities. One common type of priority is a background type request with little or no priority assigned to it. These are often combined in a scheduler with requests having a higher level of priority, such as best effort priority requests. When the different priority types are processed concurrently, overall throughput performance for a storage device may suffer if the scheduler does not send lower priority requests to the storage device while higher priority requests are still processing on the storage device. This type of circumstance often results in a dramatic negative impact on system throughput.
Real-time access requests have a higher priority than either best effort or background priority requests. Concurrently processing real-time requests with lower level priority requests is especially burdensome in some environments. The potential for complications, such as starvation, is even more acute because real-time disk access requests are usually associated with some level of guaranteed near immediate access for I/O data. In attempting to meet these guarantees, a scheduler typically places further limits upon total system efficiency and throughput. Furthermore, not meeting, or missing guaranteed access deadlines is another type of difficulty associated with scheduling real-time access requests. All of these difficulties are associated with scheduling real-time access requests. These difficulties are often compounded when scheduling real-time access requests as part of a mixture of real-time and lower priority requests.